//创建节点 
class Node{
    constructor(element){
        this.element = element;  //值
        this.left = null;        //左侧子节点
        this.right = null;       //右侧子节点
    }
}

class Tree{
    constructor(){
        this.root = null; //根
    }
    //左侧子节点比父节点的值小   右侧子节点比父节点的值大
    //插入
    insert(element){
        //1.创建节点
        let node = new Node(element); 
        //2.判断树是否为空
        if(this.root === null){
            //树为空
            this.root = node;
        }else{
            //树不为空
            this.insertNode(node,this.root)//15  20
        }
    }

    //插入节点
    insertNode(newNode,rootNode){
        //1.判断插入值和父级节点比较
        if(newNode.element < rootNode.element){
            //放在左侧
            if(rootNode.left === null){
                rootNode.left = newNode;
            }else{
                this.insertNode(newNode,rootNode.left); //15 10
            }
        }else{
            //放在右侧
            if(rootNode.right === null){
                rootNode.right = newNode;
            }else{
                this.insertNode(newNode,rootNode.right); //15  13
            }
        }
    }


    //查找最小值
    min(){
        return this.minNode(this.root);
    }

    minNode(rootNode){
        while(rootNode.left != null){
            rootNode = rootNode.left;
        }
        return rootNode
    }

    //查找最大值
    max(){
        return this.maxNode(this.root);
    }

    maxNode(rootNode){
        while(rootNode.right != null){
            rootNode = rootNode.right;
        }
        return rootNode
    }

    //搜索
    search(element){
        return this.searchNode(this.root,element); //true  false
    }

    searchNode(node,element){
        //1.判断node是否为空
        if(node === null){
            return false
        }

        //2.树不为空
        if(element < node.element){
            //左侧去搜索
            return this.searchNode(node.left,element); //true
        }else if(element > node.element){
            //右侧去搜索
            return this.searchNode(node.right,element);//false
        }else{
            return true
        }
    }

}

let tree = new Tree();

tree.insert(20);

tree.insert(10);

tree.insert(9);

tree.insert(13);

tree.insert(15);

console.log(tree.max());

console.log(tree.remove(9));//false